// https://www.lintcode.com/problem/remove-nth-node-from-end-of-list/description?_from=ladder&&fromId=6

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    // ListNode * removeNthFromEnd(ListNode * head, int n) {
    //     int len = 0;
    //     ListNode * dummy = new ListNode(-1);
    //     dummy->next = head;
    //     ListNode * tmp = dummy;
    //     while (tmp)
    //     {
    //         len++;
    //         tmp = tmp->next;
    //     }
    //     tmp = dummy;
    //     int idx = len - n - 1;
    //     while (idx--)
    //     {
    //         tmp = tmp -> next;
    //     }
    //     tmp->next = tmp->next->next;
    //     return dummy->next;
    // }
    
    
    // 法二：双指针
    ListNode * removeNthFromEnd(ListNode * head, int n) {
        ListNode * dummy = new ListNode(-1);
        dummy->next = head;
        while (n--)
        {
            head = head->next;
        }
        ListNode * tmp = dummy;
        while (head)
        {
            head = head->next;
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;
        return dummy->next;
    }
};